#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title025.py 
@version:
@time: 2023/05/14
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
"""
# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


import queue


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        ans = []

        def bfs() -> None:
            q = queue.Queue()
            q.put((root, 1))
            while not q.empty():
                cur, dep = q.get()
                if len(ans) < dep:
                    ans.append([])
                ans[-1].append(cur.val)
                if cur.left: q.put((cur.left, dep + 1))
                if cur.right: q.put((cur.right, dep + 1))

        bfs()
        return ans


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # 层序遍历的办法是 queue 是针对下一行的
        if not root:
            return []
        queue = [root]
        ans = []
        while queue:
            nodes = queue
            queue = []
            ans.append([node.val for node in nodes])
            for node in nodes:
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans
